package com.julius.design.suanfa.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @author julius
 * @date 2021-10-27 上午 10:09
 * <p>
 *      请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
 *      https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
 * </p>
 */
public class LevelOrder3 {


    /**
     * 此方法，需要优化空间复杂度
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }


        List<List<Integer>> ans = new ArrayList<>();

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        //层数
        int level = 0;
        while(!queue.isEmpty()){
            level++;
            //每层的元素个数
            int size = queue.size();
            List<Integer> temp = new ArrayList<>();
            Stack<Integer> stack = new Stack<>();
            for(int i = 0;i < size ;i++){
                TreeNode tNode = queue.poll();
                if(level % 2 != 0){
                    //奇数层  左 --》 右
                    temp.add(tNode.val);
                }else{
                    //偶数层  右 --》 左
                    stack.push(tNode.val);
                }
                if(tNode.left != null) queue.offer(tNode.left);
                if(tNode.right != null) queue.offer(tNode.right);
            }
            while (!stack.isEmpty()){
                temp.add(stack.pop());
            }
            ans.add(temp);
        }
        return ans;
    }

    public static void main(String[] args) {
        //[3,9,20,null,null,15,7]
        TreeNode root = new TreeNode(3);

        TreeNode root1 = new TreeNode(9);

        TreeNode root2 = new TreeNode(20);

        TreeNode root3 = new TreeNode(15);

        TreeNode root4 = new TreeNode(7);

        root.left = root1;
        root.right = root2;

        root2.left = root3;
        root2.right = root4;

        List<List<Integer>> lists = levelOrder(root);
        for (int i = 0; i < lists.size(); i++) {
            List<Integer> list = lists.get(i);
            for (int j = 0; j < list.size(); j++) {
                System.out.print(list.get(j)+" ");
            }
            System.out.println();
        }
    }
}
